import java.util.Arrays;
import java.util.Random;

public class 排序算法 {
    //3路快排
    public static int[] sort3(int[] num){
        return sort3(num,0,num.length-1);
    }

    public static int[] sort3(int[] num,int start,int end){
        if (start >= end){
            return num;
        }
        int v = num[start];
        int i = start+1;
        int j = end;
        int it = start;
        while (i <= j){
            int temp = num[i];
            if (temp < v){
                num[i] = v;
                num[it] = temp;
                it++;
                i++;
            }else if (temp == v){
                i++;
            }else {
                while (j > i && num[j] > v){
                    j--;
                }
                num[i] = num[j];
                num[j] = temp;
                j--;
            }
        }
        sort3(num,start,it-1);
        sort3(num,j+1,end);
        return num;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int[] num = new int[10000];
        for (int i = 0; i < 10000; i++) {
            Random random = new Random();
            num[i] = random.nextInt(1000000);
        }
        System.out.println(Arrays.toString(sort3(num)));
        long end = System.currentTimeMillis();
        System.out.println(end-start);

    }
}

